package com.algomypractice.linkedlist;

/**
 * @author: ZhouBert
 * @date: 2019/6/4
 * @description: LRU算法 用Array实现
 */
public class LRUBasedArray<T> {

	/**
	 * 默认容量(不再对容量进行扩容，于是有了LRU)
	 */
	private final int DEFAULT_CAPACITY = 1 << 3;

	/**
	 * 缓存数据
	 */
	private T[] data;
	/**
	 * 实际大小
	 */
	private int size;

	/**
	 * 默认构造函数
	 */
	public LRUBasedArray() {
		data = (T[]) new Object[DEFAULT_CAPACITY];
		this.size = 0;
	}

	/**
	 * 设置容量
	 *
	 * @param capacity
	 */
	public LRUBasedArray(int capacity) {
		data = (T[]) new Object[capacity];
		this.size = 0;
	}

	/**
	 * 模拟访问个值
	 *
	 * @param object
	 */
	public void offer(T object) {
		///记录访问的索引的位置
		int index = -1;
		for (int i = 0; i < size; i++) {
			if (data[i].equals(object)) {
				index = i;
				break;
			}
		}
		//木有访问到到旧数据
		if (index == -1) {
			if(isFull()){
				rightShift(size-1);

			}else {
				rightShift(size);
				size++;
			}
			data[0] = object;
		} else {
			rightShift(index);
			data[0] = object;
		}
	}

	/**
	 * 若缓存中有指定的值，则更新位置
	 *
	 * @param end
	 */
	public void update(int end) {
		T target = data[end];
		rightShift(end);
		data[0] = target;
	}

	/**
	 * 缓存数据到头部，但是先右移
	 */
	public void cache(T object, int end) {

	}

	private boolean isFull(){
		return size==DEFAULT_CAPACITY;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < size; i++) {
			sb.append(data[i]);
			sb.append(" ");
		}
		return sb.toString();
	}

	/**
	 * end 左边的数据统一右移一位
	 */
	private void rightShift(int end) {
		if (end < 0 || end >= DEFAULT_CAPACITY) {
			throw new IllegalArgumentException("end 索引位置错误！");
		}
		//右移 从大到小
		for (int i = end - 1; i > -1; i--) {
			data[i + 1] = data[i];
		}
	}


	public static void main(String[] args) {
		System.out.println("======无参测试========");
		LRUBasedArray<Integer> lru = new LRUBasedArray<Integer>();
		lru.offer(1);
		lru.offer(2);
		lru.offer(3);
		lru.offer(4);
		lru.offer(5);
		System.out.println(lru);
		lru.offer(6);
		lru.offer(7);
		lru.offer(8);
		lru.offer(9);
		System.out.println(lru);
		lru.offer(1);
		lru.offer(3);
		System.out.println(lru);
		lru.offer(3);
		System.out.println(lru);
	}
}
